// 单向链表
public class MyNode {
    // 头节点
    private Node head;
    // 尾节点
    private Node last;
    //   链表实际长度
    private int size;

//    链表定义
    public static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }

//    链表插入
    public void insert(int data,int index) throws Exception{
        if (index < 0 || index > size){
            throw new IndexOutOfBoundsException("超出节点实际长度");
        }
        Node insertedNode = new Node(data);
        if (size == 0){
            head = insertedNode;
            last = insertedNode;
        }else if (index == 0){
//            插入头部
            insertedNode.next = head;
            head= insertedNode;
        } else if (index == size) {
            last.next = insertedNode;
            last = insertedNode;
        } else {
            Node prevNode = get(index -1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        size ++;
    }

//    删除元素节点
    public Node remove (int index) throws Exception{
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("超出链表实际长度");
        }
//        删除头节点
        Node removeNode = null;
        if (index == 0){
            removeNode = head;
            head = head.next;
        }else if (index == size -1){
            Node prevNode = get(index -1);
            removeNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        }else {
            Node prevNode = get(index -1);
            Node nextNode = prevNode.next.next;
            removeNode = prevNode.next;
            prevNode.next = nextNode;
        }
        size --;
        return removeNode;
    }

//    查找元素位置
    public Node get(int index)throws Exception{
        if (index < 0 || index >= size){
            throw new IndexOutOfBoundsException("超出链表长度");
        }
        Node temp = head;
        for (int i=0; i<index ; i++){
            temp = temp.next;
        }
        return temp;
    }

//    输出
    public void outPut(){
        Node temp = head;
        while (temp != null){
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    public static void main(String[] args) throws Exception {
        MyNode node = new MyNode();
        node.insert(1,0);
        node.insert(2,1);
        node.insert(3,2);
        node.insert(3,3);
        node.insert(4,4);
        node.insert(5,5);
        node.remove(3);
        node.outPut();
    }
}
